{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Numbers with Unique Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countNumbersWithUniqueDigits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计各位数字都不同的数字个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你一个整数 <code>n</code> ，统计并返回各位数字都不同的数字 <code>x</code> 的个数，其中 <code>0 &lt;= x &lt; 10<sup>n</sup></code><sup>&nbsp;</sup>。\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>91\n",
    "<strong>解释：</strong>答案应为除去 <code>11、22、33、44、55、66、77、88、99 </code>外，在 0 ≤ x &lt; 100 范围内的所有数字。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 0\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 8</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-numbers-with-unique-digits](https://leetcode.cn/problems/count-numbers-with-unique-digits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-numbers-with-unique-digits](https://leetcode.cn/problems/count-numbers-with-unique-digits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def countNumbersWithUniqueDigits(self, n):\n",
    "    \"\"\" \n",
    "    :type n: int\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    if n == 0:\n",
    "      return 1\n",
    "    elif n == 1:\n",
    "      return 10\n",
    "\n",
    "    ans = 10\n",
    "    cur = 9\n",
    "    for i,j in zip( range( 1, min( n, 10 ) ), range( 9, -1, -1 ) ):\n",
    "      cur *= j\n",
    "      ans += cur\n",
    "\n",
    "    return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        if n<1:\n",
    "            return 1\n",
    "    \n",
    "        res=0\n",
    "        for i in range(1,n+1):\n",
    "            res+=self.count(i)\n",
    "        \n",
    "        return res\n",
    "            \n",
    "    \n",
    "    \n",
    "    def count(self,n):\n",
    "        if n==1:\n",
    "            return 10\n",
    "        res=9\n",
    "        for i in range(9-n+2,10):\n",
    "            res*=i\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #纯粹的数学题，加上动态规华\n",
    "        An=[1,10]\n",
    "        if n<2:return An[n]\n",
    "        while len(An)-1!=n and len(An)<=10:\n",
    "            t=9\n",
    "            for i in range(9,10-len(An),-1):\n",
    "                t*=i\n",
    "            An.append(t+An[-1])\n",
    "        return An[-1]\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = [1, 9]\n",
    "res = 9\n",
    "fac = 9\n",
    "while fac:\n",
    "    res *= fac\n",
    "    fac-=1\n",
    "    dp.append(res)\n",
    "\n",
    "for i in range(1, len(dp)-1):\n",
    "    dp[i] += dp[i-1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n > 10:\n",
    "            n = 10\n",
    "        return dp[n]\n",
    "        \n",
    "            \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n==0:\n",
    "            return 1\n",
    "        else:\n",
    "            c=0\n",
    "            t=9\n",
    "            for i in range(1,n+1):\n",
    "                if i==1:\n",
    "                    t=10\n",
    "                else:\n",
    "                    for j in range(2,i+1):\n",
    "                        t=t*(10-j+1)\n",
    "                c+=t\n",
    "                t=9\n",
    "            return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "       \n",
    "        if not n:\n",
    "            return 1\n",
    "        res, muls = 10, 9\n",
    "        for i in range(1, min(n,10)):\n",
    "            muls *= 10 - i\n",
    "            res += muls\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 10\n",
    "        ans = 10\n",
    "        f = 9\n",
    "        for i in range(2, n + 1):\n",
    "            f *= (11 - i)\n",
    "            ans += f\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        \n",
    "        #为啥我原来想的动态规划要规划重复数字呢？？\n",
    "        if n==0:\n",
    "            return 1\n",
    "        res = [[1,9,10]]\n",
    "        for i in range(2,min(n+1,11)):\n",
    "            res.append([res[-1][1]*(i-1),res[-1][1]*(10-i)])\n",
    "            res[-1].append(res[-1][0]+res[-1][1]+res[-2][-1])\n",
    "            \n",
    "        return res[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 10\n",
    "        n = min(n, 10)\n",
    "        dp = [9] * (n + 1)\n",
    "        res = 10\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = dp[i - 1] - 1\n",
    "            tmp = 1\n",
    "            while i - 1 >= 0:\n",
    "                tmp *= dp[i - 1]\n",
    "                i -= 1\n",
    "            res += tmp\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 10\n",
    "        res = 10\n",
    "        for i in range(2, n + 1):\n",
    "            cur = 9\n",
    "            for j in range(i - 1):\n",
    "                cur *= (9 - j)\n",
    "            cur += res\n",
    "            res = cur\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 1\n",
    "\n",
    "        n=min(n,10)\n",
    "        res=10\n",
    "        cur=9\n",
    "        k=9\n",
    "\n",
    "        for i in range(2,1+n):\n",
    "            cur*=k\n",
    "            k-=1\n",
    "            res+=cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 10\n",
    "        cnt = 10\n",
    "        factor = 8\n",
    "        factorial = 9\n",
    "        for i in range(2, min(n, 10)+1):\n",
    "            cnt += 9 * factorial\n",
    "            factorial *= factor\n",
    "            factor -= 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        ##  n=1 各位数不同的数字个数  10\n",
    "        ##  n=2时，十位可取 1~9 各位可以取0~9 - 1(十位选掉了) 9*9\n",
    "        ##  n=3时，9*9*8 + 9*9 + 10\n",
    "        if n==0:return 1\n",
    "        if n==1:return 10\n",
    "        ans = 0\n",
    "        def backtrack(candidate,curr,length):\n",
    "            if len(curr) == length:\n",
    "                nonlocal  curr_res \n",
    "                curr_res +=1\n",
    "                return\n",
    "            for i in range(len(candidate)):\n",
    "                if not curr and candidate[i] == 0: #排除第一个数字为0\n",
    "                    continue\n",
    "                curr.append(candidate[i])\n",
    "                backtrack(candidate[:i]+candidate[i+1:],curr,length) #回溯\n",
    "                curr.pop()\n",
    "\n",
    "        nums = [i for i in range(10)]\n",
    "        dp = 10\n",
    "        for i in range(2,n+1):\n",
    "            curr_res = 0\n",
    "            backtrack(nums,[],i)\n",
    "            dp = dp + curr_res\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        self.maxNum = str(10 ** n - 1)\n",
    "        self.cache = dict()\n",
    "        return self.countNumUniqueDigitsHelper(0, True, True, 0, False)\n",
    "        \n",
    "    def countNumUniqueDigitsHelper(self, i, hasLeadingZero, isLimit, usedDigits, hasDuplicate):\n",
    "        if i == len(self.maxNum):\n",
    "            return 1 if not hasDuplicate else 0\n",
    "        \n",
    "        key = (i, hasLeadingZero, isLimit, usedDigits, hasDuplicate)\n",
    "        if key in self.cache:\n",
    "            return self.cache[key]\n",
    "\n",
    "        count = 0\n",
    "        maxDigit = 9 if not isLimit else int(self.maxNum[i])\n",
    "        for digit in range(maxDigit + 1):\n",
    "            nextHasLeadingZero = hasLeadingZero and digit == 0\n",
    "            nextIsLimit = isLimit and digit == maxDigit\n",
    "            if nextHasLeadingZero:\n",
    "                nextUsedDigits = usedDigits\n",
    "                nextHasDuplicate = False\n",
    "            else:\n",
    "                nextUsedDigits = usedDigits | (1 << digit)\n",
    "                nextHasDuplicate = hasDuplicate or (usedDigits & (1 << digit)) != 0\n",
    "            count += self.countNumUniqueDigitsHelper(i+1, nextHasLeadingZero, nextIsLimit, nextUsedDigits, nextHasDuplicate)\n",
    "        self.cache[key] = count\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        n = 10 ** n - 1\n",
    "        MAX = 10\n",
    "        digits, len_n = [0] * MAX, 0\n",
    "        dp = [[-1] * (1 << MAX) for _ in range(MAX)]\n",
    "        def getDp(digits, pos, sta, lead, limit):\n",
    "            if pos == -1: return 1\n",
    "            if not lead and not limit and dp[pos][sta] != -1: return dp[pos][sta]\n",
    "            up = digits[pos] if limit else 9\n",
    "            ans = 0\n",
    "            for i in range(up + 1):\n",
    "                if i == 0 and lead:\n",
    "                    ans += getDp(digits, pos - 1, sta, lead and i == 0, limit and i == up)\n",
    "                else:\n",
    "                    if sta & (1 << i):\n",
    "                        continue\n",
    "                    ans += getDp(digits, pos - 1, sta | (1 << i), lead and i == 0, limit and i == up)\n",
    "            if not lead and limit:\n",
    "                dp[pos][sta] = ans\n",
    "            return ans\n",
    "\n",
    "        while n:\n",
    "            digits[len_n] = n % 10\n",
    "            n //= 10\n",
    "            len_n += 1\n",
    "        return getDp(digits, len_n - 1, 0, True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        if n == 0:return 1\n",
    "        count = min(n, 10)\n",
    "        res = 0\n",
    "        for i in range(1, n+1):\n",
    "            tmp = 9\n",
    "            if i == 1:\n",
    "                tmp = 10\n",
    "            else:\n",
    "                for j in range(i-1):\n",
    "                   tmp *=  9-j\n",
    "            res += tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 初始思路\n",
    "NUM_CHOICES = [9,] + list(range(9, 0, -1))\n",
    "print(NUM_CHOICES)  \n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        res = product = 1\n",
    "        for i in range(n):\n",
    "            product *= NUM_CHOICES[i]\n",
    "            res += product\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "        if n == 0:\n",
    "            return dp[-1]\n",
    "        dp[1] = 10\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = dp[i-1] * (12-i) - dp[i-2] * (11-i)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 1\n",
    "        if n==1:\n",
    "            return 10\n",
    "        res,c=10,9\n",
    "        for i in range(n-1):\n",
    "            c*=9-i\n",
    "            res+=c\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "  \n",
    "        # @cache\n",
    "        def f(i, mask, isnum):\n",
    "            if i == len(s): return 1 \n",
    "            if isnum and dp[i][mask] != -1: return dp[i][mask]\n",
    "            res = 0 if isnum else f(i + 1, mask, False) # 可以跳过当前数位\n",
    "            down = 0 if isnum else 1\n",
    "            \n",
    "            for d in range(down, 10):  # 枚举要填入的数字 d\n",
    "                if mask >> d & 1 == 0:  # d 不在 mask 中\n",
    "                    res += f(i + 1, mask | (1 << d), True)\n",
    "            dp[i][mask] = res;\n",
    "            return res\n",
    "        s = '9' * n\n",
    "        dp = [[-1] * 1024 for _ in range(len(s))]\n",
    "        return f(0, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        elif n == 1:\n",
    "            return 10\n",
    "        elif n == 2:\n",
    "            return 91 \n",
    "        dp[0] = 1\n",
    "        dp[1] = 10\n",
    "        dp[2] = 91\n",
    "        for i in range(3,n+1):\n",
    "            dp[i] = dp[i-1] + (dp[i-1]-dp[i-2])*(10-i+1)\n",
    "        print(dp)\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 1\n",
    "        elif n==1:\n",
    "            return 10\n",
    "        elif n==2:\n",
    "            return 91\n",
    "        elif n==3:\n",
    "            return 739\n",
    "        elif n==4:\n",
    "            return 5275\n",
    "        elif n==5:\n",
    "            return 32491\n",
    "        elif n==6:\n",
    "            return 168571\n",
    "        elif n==7:\n",
    "            return 712891\n",
    "        elif n==8:\n",
    "            return 2345851"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        ans = [1, 9, 81, 648, 4536, 27216, 136080, 544320, 1632960, 3265920, 3265920]\n",
    "        return sum(ans[:n + 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 10\n",
    "        res, cur = 10, 9\n",
    "        for i in range(n - 1):\n",
    "            cur *= 9 - i\n",
    "            res += cur\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(m, s):\n",
    "    if m == 0:\n",
    "        return 1\n",
    "    res = 0\n",
    "    for i in range(10):\n",
    "        if s >> i & 1:\n",
    "            res += dfs(m - 1, s ^ (1 << i))\n",
    "    return res\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 10\n",
    "        res = 1 # 0\n",
    "        for i in range(1, n + 1):\n",
    "            # 枚举长度\n",
    "            for j in range(1, 10):\n",
    "                res += dfs(i - 1, (1 << 10) - 1 - (1 << j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        ns = [int(c) for c in str(10 ** n - 1)]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(k, st, empty, to_border):\n",
    "            if k == len(ns):\n",
    "                if empty:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return 1\n",
    "            ans = 0\n",
    "            if empty:\n",
    "                ans += dp(k + 1, st, True, False)\n",
    "\n",
    "            for i in range(10):\n",
    "                if to_border and i > ns[k]:\n",
    "                    break\n",
    "                if empty and i == 0 and k < len(ns) - 1:\n",
    "                    continue\n",
    "                if not st[i]:\n",
    "                    lst = list(st)\n",
    "                    lst[i] = True\n",
    "                    ans += dp(k + 1, tuple(lst), False, to_border and i == ns[k])\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dp(0, tuple([False] * 10), True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        if n == 0: return 1\n",
    "        s = '9' * n\n",
    "        def digit_dp(s: str) -> int:\n",
    "            f = defaultdict(int)\n",
    "            def dp(i: int, last: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s): return 1\n",
    "\n",
    "                #如果 不受限制 且 填了数字 且 计算过   直接返回\n",
    "                if not is_limit and is_num and f[(i, last)] != 0: return f[(i, last)]\n",
    "                res = 0\n",
    "                if not is_num: res += dp(i + 1, 0, False, False)\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "\n",
    "                for d in range(1 - int(is_num), up + 1):\n",
    "                    if last >> d & 1 != 1:\n",
    "                        res += dp(i + 1, last | (1 << d), is_limit and d == up, True)\n",
    "\n",
    "                # 更新答案\n",
    "                if not is_limit and is_num: f[(i, last)] = res\n",
    "                return res\n",
    "            return dp(0, 0, True, False)\n",
    "        return digit_dp(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(i, mask, isNum):\n",
    "            if i == n:\n",
    "                return int(isNum)\n",
    "            res = 0\n",
    "            if not isNum:\n",
    "                res = f(i + 1, mask, isNum)\n",
    "            low = 0 if isNum else 1\n",
    "            for d in range(low, 10):\n",
    "                if (mask >> d & 1) == 0:\n",
    "                    res += f(i + 1, mask | (1 << d), True)\n",
    "        \n",
    "            return res\n",
    "        \n",
    "        res = f(0, 0, False)\n",
    "        return res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbersWithUniqueDigits(self, n: int) -> int:\n",
    "        s = str(10 ** n - 1)\n",
    "        @cache\n",
    "        def f(i, mask, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            ret = 0\n",
    "            if not is_num:\n",
    "                ret = f(i + 1, mask, False, False)\n",
    "            low = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(low, up + 1):\n",
    "                if (mask >> d & 1) == 0:\n",
    "                    ret += f(i + 1, mask | (1 << d), is_limit and d == up, True)\n",
    "            return ret\n",
    "        return f(0, 0, True, False) + 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
